//
//  CCTreeBase.hpp
//  leetcode
//
//  Created by hellobike07499 on 2019/8/5.
//  Copyright © 2019 hellobike07499. All rights reserved.
//

#ifndef CCTreeBase_hpp
#define CCTreeBase_hpp

#include <stdio.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

using namespace std;


class CCTreeBase{
public:
    struct TreeNode{
        TreeNode *left, *right;
        int val;
        
        TreeNode():left(NULL), right(NULL){};
        TreeNode(int i):left(NULL), right(NULL), val(i){};
    };
    
public:
    void test(){
        vector<string> contain = {"3","9","20","null","null","15","7"};
        TreeNode *tree = buildTree(contain);
        traceTreeByRange(tree);
        cout << endl;
        
        traceTreeByDeep(tree);
        cout << endl;
        
        cout << "max deep :" << treeMaxDeep(tree);
        cout << "max deep :" << treeMaxDeep1(tree);
    }
    
    void test1(){
        vector<string> treeContain = {"5","1","4","null","null","3","6"};
        TreeNode *tree = buildTree(treeContain);
        cout << "is Bst :" << (isValidBST(tree) ? "yes" : "no");
        cout << endl;
        
        treeContain = {"10","5","15","null","null","6","20"};
        tree = buildTree(treeContain);
        cout << "is Bst :" << (isValidBST(tree) ? "yes" : "no");
        cout << endl;
    }
    
    void test2(){
        vector<string> t = {"1","0"};
        TreeNode *tree = buildTree(t);
        
        cout << "isSymmetric :" << (isSymmetric(tree) ? "yes" : "no")<<endl;
        
        t = {"1","2","2","null","3","null","3"};
        tree = buildTree(t);
        cout << "isSymmetric :" << (isSymmetric(tree) ? "yes" : "no")<<endl;
    }
    
    void test3(){
        vector<string> t = {"3","9","20","null","null","15","7"};
        TreeNode *tree = buildTree(t);
        vector<vector<int>> level = levelOrder(tree);
        
        cout << "tree" << endl;
    }
    
    void test4(){
        vector<int> t = {-10,-3,0,5,9};
        TreeNode *tree = sortedArrayToBST(t);
        traceTreeByRange(tree);
        cout << "sorted" << endl;
    }
private:
    
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.size() == 0) return NULL;
        
        int center = ((int)nums.size() - 1 ) / 2;
        TreeNode * p = new TreeNode;
        p->val = nums[center];
        
        if(center > 0){
            vector<int> l(nums.begin(), nums.begin() + (center));
            TreeNode *left = sortedArrayToBST(l);
            p->left = left;
        }
        
        if((center + 1) < nums.size()){
            vector<int> r(nums.begin() + (center + 1), nums.end());
            TreeNode *right = sortedArrayToBST(r);
            p->right = right;
        }
        
        return p;
    }
    
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> all ;
        if(!root) return all;
        
        vector<TreeNode*> trace;
        TreeNode *move = root;
        trace.push_back(move);
        
        while (!trace.empty()) {
            vector<int> level;
            int count = (int)trace.size();
            
            for (int i = 0; i < count; i++) {
                TreeNode *c = trace[i];
                if(c->left) trace.push_back(c->left);
                if(c->right) trace.push_back(c->right);
                
                level.push_back(c->val);
            }
            
            if(count > 0){
                trace.erase(trace.begin() , trace.begin() + count);
            }
            
            all.push_back(level);
        }
        
        return all;
    }
    
    bool isValidBST(TreeNode* root) {
        if(!root) return true;
        
        TreeNode *move = root, *pre = NULL;
        queue<TreeNode*> traceNode;
        
        while(move && !traceNode.empty()){
            //move to left
            while(move){
                traceNode.push(move);
                move = move->left;
            }
            
            TreeNode *current = traceNode.front();
            traceNode.pop();
            
            if(pre && pre->val >= current->val) return false;
            pre = current;
            if(current->right) move = current->right;
        }
        
        return true;
    }
    
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        
        TreeNode *left = root->left;
        TreeNode *right = root->right;
        stack<TreeNode*> leftTrace;
        stack<TreeNode*> rightTrace;
        
        
        while((left || !leftTrace.empty()) || (right || !rightTrace.empty())){
            while (left) {
                leftTrace.push(left);
                left = left->left;
            }
            while (right) {
                rightTrace.push(right);
                right = right->right;
            }
            
            if(leftTrace.size() != rightTrace.size()) return false;
            
            TreeNode *cl = leftTrace.top(); leftTrace.pop();
            TreeNode *cr = rightTrace.top(); rightTrace.pop();
            
            if(cl->val != cr->val) return false;
            
            left = cl->right;
            right = cr->left;
        }
        
        return true;
    }
    
    void traceTreeByRange(TreeNode *tree){
        if(!tree) return ;
        
        std::queue<TreeNode*> treeNode;
        treeNode.push(tree);
        
        while(!treeNode.empty()){
            TreeNode *current = treeNode.front();
            treeNode.pop();
            
            cout << current->val;
            cout << ", " ;
            
            if(current->left){
                treeNode.push(current->left);
            }
            
            if(current->right){
                treeNode.push(current->right);
            }
        }
    }
    
    void traceTreeByDeep(TreeNode *tree){
        if(!tree) return;
        
        stack<TreeNode*> trace;
        trace.push(tree);
        
        while(!trace.empty()){
            TreeNode *current = trace.top();
            trace.pop();
            
            cout << current->val ;
            cout << " ,";
            
            if(current->right){
                trace.push(current->right);
            }
            
            if(current->left){
                trace.push(current->left);
            }
        }
    }
    
    int treeMaxDeep(TreeNode *tree){
        if(!tree) return 0;
        
        int leftLayer = treeMaxDeep(tree->left);
        int rightLayer = treeMaxDeep(tree->right);
        
        int max = (leftLayer > rightLayer ? leftLayer : rightLayer) + 1;
        return max;
    }
    
    int treeMaxDeep1(TreeNode *tree){
        if(!tree) return 0;
        
        stack<TreeNode*> traceNode;
        traceNode.push(tree);
        
        int trace = 1;
        while(!traceNode.empty()){
            TreeNode *current = traceNode.top();
            traceNode.pop();
            
            if(current->right){
                traceNode.push(current->right);
            }
            
            if(current->left){
                traceNode.push(current->left);
            }
            if(current->left || current->right){
                trace++;
            }
        }
        
        return trace;
    }
    
    TreeNode* buildTree(vector<string>& queue){
        if(queue.size() == 0) return NULL;
        
        TreeNode *header = NULL;
        std::queue<TreeNode*> treenNode;
        vector<string>::iterator item = queue.begin();
        while(item != queue.end()){
            TreeNode *parent = NULL;
            if(treenNode.size() > 0){
                parent = treenNode.front();
                treenNode.pop();
            }
            

            if(!header){
                if((*item).compare("null") == 0){
                    return NULL;
                }
                
                header = new TreeNode(stoi(*item));
                treenNode.push(header);
                item++;
                continue;
            }
            
            if(parent){
                if((*item).compare("null") != 0){
                    parent->left = new TreeNode(stoi(*item));
                }
                
                item++;
            }
            if(parent && item != queue.end()){
                if((*item).compare("null") != 0){
                    parent->right = new TreeNode(stoi(*item));
                }
                
                item++;
            }
            
            
            if(parent && parent->left){
                treenNode.push(parent->left);
            }
            if(parent && parent->right){
                treenNode.push(parent->right);
            }
        }
        
        return header;
    }
    
    
};

#endif /* CCTreeBase_hpp */
